/**
 * 给定字符串S和K，每次将当前字符串的前K个字母删除，
 * 并在字符串后接上K个字母，接上的这K个字母可以根据需要任意安排
 * 问要操作几次，可以得回原来的字符串。
 * 至少要操作1次。
 * 假设删除到第3个可以完成任务，则
 * xxxyyyyy
 * yyyyy...
 * 这说明剩下的y部分是原字符串的前缀。即前后缀要相等，特征向量。
 * 因此首先求出特征向量，注意特征向量只记录最长的特征数。
 * xx.....xx
 * 对字符串的最后一个位置，需要求出所有满足形如上述条件的特征数
 * 然后根据切的位置依次判断即可。
 */
class Solution {
public:
    int minimumTimeToInitialState(string word, int k) {
        int n = word.length();
        vector<int> vec(n, 0);
        calcNext(word.begin(), n, vec);
        
        vector<int> tmp;
        tmp.emplace_back(vec.back());
        while(tmp.back()) tmp.emplace_back(vec[tmp.back() - 1]);
        
        int now = 0;
        int cur = k;
        int ans = 0;
        while(1){
            ans += 1;
            int left = n - cur;
            if(left <= 0) return ans;
            while(tmp[now] > left){
                now += 1;
            }
            assert(now >= 0);
            if(tmp[now] == left){
                return ans;
            }

            cur += k;
        }
        return ans;  
    }

    template<typename IT>
    void calcNext(IT begin, int n, vector<int> & next) {
        next.assign(n, 0);
        for(int i=1;i<n;++i){
            int k = next[i - 1];
            while(k > 0 and *(begin + i) != *(begin + k)){
                k = next[k - 1];
            }
            next[i] = (*(begin + i) == *(begin + k)) ? k + 1 : 0;
        }
        return;
    }    
};